package gee

import "strings"

// 缺陷：当路由树是链表结构时，要找到叶子结点 循环趋向于N
// 解决：可以尝试压缩前缀树，当前缀树的子节点是链表时，直接把叶子节点升级为父节点（handler 保存到父节点 而不是子节点）
// -----------------可以这样做事因为当路由树一旦生成就不会在更新路由，所以方便压缩

/**
 * @Author: yang
 * @Description： 路由树--（前缀树）
 * @Date: 2021/11/5 16:52
 */
type node struct {
	pattern  string      // 完整路由（叶子节点不为空），例如 /p/:lang
	handler  HandlerFunc // 路由 操作
	part     string      // 路由中的一部分，例如 :lang
	children []*node     // 子节点，例如 [doc, tutorial, intro]
	isWild   bool        // 是否精确匹配，part 含有 : 或 * 时为true
}

/**
 * @Author: yang
 * @Description：第一个匹配成功的节点，用于插入 (找路径)
 * @Date: 2021/11/5 17:29
 */
func (n *node) matchChild(part string) *node {
	for _, child := range n.children {
		if child.part == part || child.isWild {
			return child
		}
	}
	return nil
}

// 所有匹配成功的节点，用于查找
func (n *node) matchChildren(part string) []*node {
	nodes := make([]*node, 0)
	for _, child := range n.children {
		if child.part == part || child.isWild {
			nodes = append(nodes, child)
		}
	}
	return nodes
}

/**
 * @Author: yang
 * @Description：路有树--递归生成树
 * @Date: 2021/11/5 17:01
 */
func (n *node) insert(pattern string, parts []string, height int, handler HandlerFunc) {

	// 树高度 == 节点数 退出
	if len(parts) == height {
		n.pattern = pattern
		n.handler = handler
		return
	}

	part := parts[height]

	// 获取插入节点
	child := n.matchChild(part)
	if child == nil {
		child = &node{part: part, isWild: part[0] == ':' || part[0] == '*'}
		n.children = append(n.children, child)
	}
	child.insert(pattern, parts, height+1, handler)
}

/**
 * @Author: yang
 * @Description： 路由树--递归寻找叶子节点
 * @Date: 2021/11/5 17:54
 */
func (n *node) search(parts []string, height int) *node {

	// 路由树--叶子节点
	if len(parts) == height || strings.HasPrefix(n.part, "*") {
		if n.pattern == "" {
			return nil
		}
		return n
	}

	part := parts[height]
	children := n.matchChildren(part)

	for _, child := range children {
		result := child.search(parts, height+1)
		if result != nil {
			return result
		}
	}

	return nil
}
